package graph.day14;

import java.util.Stack;

public class Leetcode_844 {

    public boolean backspaceCompare(String s, String t) {
        // 本题也可以用Stringbuilder模拟栈，可以省去栈中元素的比较
        Stack<String> stack1 = new Stack<>();
        Stack<String> stack2 = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '#') {
                if (!stack1.isEmpty()) {
                    stack1.pop();
                }
            } else {
                stack1.push(String.valueOf(s.charAt(i)));
            }
        }
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == '#') {
                if (!stack2.isEmpty()) {
                    stack2.pop();
                }
            } else {
                stack2.push(String.valueOf(t.charAt(i)));
            }
        }
        if (stack1.size() != stack2.size()) return false;
        while (!stack1.isEmpty()) {
            if (!stack1.pop().equals(stack2.pop())) return false;
        }
        return true;
    }
}
